package Midium;

// 5. 最长回文子串
// 思路：正反向计算哈希，相同则说明是回文串，相比直接两两字符进行比较，减少了比较的次数
// 注意：哈希值不能超过long
public class Solution5 {
    public static String longestPalindrome(String s) {
        if (s.length() == 0)
            return "";
        if (s.length() == 1)
            return s;
        int i = 1, j = 0;
        String sub = s.substring(0, 1);//如果最后没有回文串，那就返回第一个字符，因为第一个字符本身也是回文串
        int maxLen = 0;
        while (j < s.length()) {
            for (; i < s.length(); i++) {
                if (s.charAt(j) == s.charAt(i))
                    break;
            }
            if (i < s.length() && isPalindrome(s.substring(j, i + 1))) {
                // 如果新的回文子串比原来的大，才更新
                if (s.substring(j, i + 1).length() > maxLen) {
                    sub = s.substring(j, i + 1);
                    maxLen = sub.length();
                }
            }
            i++;
            if (i - 1 == s.length()) {
                j++;
                if (maxLen > s.length() / 2)
                    break;
                i = j + 1;
            }
        }
        return sub;
    }

    // 事实证明直接比较会比计算哈希要快
    public static boolean isPalindrome(String s){
        for(int i = 0 , j = s.length()-1 ; i<s.length()/2 ; i++,j--)
            if(s.charAt(i)!=s.charAt(j))
                return false;
        return true;
    }

    public static boolean hashCalculation(String s) {
        long forward = 0, reverse = 0;
        //奇数则算[0,len/2]和[len/2,len)，偶数则算[0,len/2)和[len/2,len)
        int len = s.length();
        int i = 0, j = len - 1;
        int k = 0;
        for (; i < len / 2; i++,k++) {
            forward += Math.pow(26, k) * s.charAt(i);
//            if (forward > Math.pow(2, 16))
//                forward = (long) (forward / Math.pow(20, i));
            if(k%5==0)
                k=0;
        }
        if (len % 2 != 0) {
            //len为奇数奇数
            forward += Math.pow(26, k) * s.charAt(i);
        }
        for (k = 0; j > len / 2 - 1; j--, k++) {
            reverse += Math.pow(26, k) * s.charAt(j);
//            if (reverse > Math.pow(2, 16))
//                reverse = (long) (reverse / Math.pow(20, i));
            if(k%5==0)
                k=0;
        }
        return forward == reverse;
    }

    public static void main(String[] args) {
        System.out.println(longestPalindrome("abbcccbbbcaaccbababcbcabca"));
    }
}
